A number of different copy protection techniques have been developed for protecting digital recordings and other types of copyrighted content material from unauthorized use. In many such techniques, the content material is encrypted such that it can only be decrypted using a key accessible to a compliant device. For example, an access control system for copy-protected content material may effect a key exchange with the particular compliant device, using a Diffie-Hellman key exchange or other public key cryptography technique. The access control system then uses the exchanged key to encrypt a decryption key for decrypting the content material, and supplies the decryption key to the device.
In this manner, only the intended compliant device can decrypt the content material. Generally, the access control system does not undertake the key exchange until after the particular compliant device identifies itself, and, in most cases, authenticates this identification, typically via an encrypted signature that can be verified. Other copy protection techniques that rely in whole or in part upon an identification of a receiver or other device are common in the art.
An adversary of the above-described access control system can subvert the copy protection technique by imitating a compliant device. That is, techniques are common in the art for replicating a compliant device, such that, in operation, the replicated device is virtually indistinguishable from the original. A common unauthorized business practice is the sale of “black market” or “pirated” imitations of replicated compliant devices that are intended for use in gaining unauthorized access to copy-protected content material.
In order to counteract such an adversary, device manufacturers, content providers and other issuing authorities typically publish revocation lists, itemizing each identifier that has been determined to be no longer valid. In principle, the access control system receives an identifier from the intended receiving device, compares this identifier to the list of all invalidated identifications, then grants or denies access accordingly. Each issuing authority periodically publishes a list of the recently revoked identifiers, and this list is communicated to each access control system, using a variety of techniques.
For example, if the access control system is a set-top box that only provides broadcast content material to a compliant recorder or display device, the revocation list can be transmitted to the set-top box from the provider of the broadcast services. If the access control system is a consumer digital versatile disk (DVD) player that only plays back a DVD to a compliant display device, the latest revocation list can be embedded within commercial DVD recordings. When the user of the DVD player plays a recently purchased or rented DVD recording, the DVD player reads the embedded list. When the access control system receives a new revocation list, it updates a locally stored list of revocations accordingly. Because the local revocation list at the access control system is of finite size, each access control system is typically configured to delete the oldest revocations when space is required for newer revocations.
A significant drawback of conventional techniques for managing the above-described revocation lists is the amount of computation time and other access control system resources required to determine if a given entity has been revoked. For example, it is generally necessary when using the conventional list management techniques to implement a complete search of a revocation list in order to determine if a given entity initiating communication is authorized to do so. In addition, each time a local revocation list in an access control system is modified, separate determinations generally must be made for a number of other devices, even though the system may be regularly in contact with these devices.
A need therefore exists for improved techniques for managing revocations lists, such that the amount of system resources consumed in the list management process is reduced.